'''
https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/description/
'''
from functools import cache
from typing import List

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        @cache
        def f(i, rest):
            if i == n:
                return 0
            res = f(i+1, rest)
            sum_t = 0
            for t in range(min(len(piles[i]), rest)):
                sum_t += piles[i][t]
                res = max(res, sum_t + f(i+1, rest - t - 1))
            return res
        return f(0, k)

    # dp 打表
    def maxValueOfCoins2(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        # 第一维度依赖后边的，第二维度依赖前边的
        for i in range(n-1, -1, -1):
            for rest in range(k + 1):
                res = dp[i+1][rest]
                sum_t = 0
                for t in range(min(len(piles[i]), rest)):
                    sum_t += piles[i][t]
                    res = max(res, sum_t + dp[i+1][rest - t - 1])
                dp[i][rest] = res
        return dp[0][-1]

    # dp记忆化搜索
    def maxValueOfCoins3(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        A = [0] * (k + 1)
        # 第一维度依赖后边的，第二维度依赖前边的
        for i in range(n-1, -1, -1):
            B = [0] * (k + 1)
            for rest in range(k + 1):
                res = A[rest]
                sum_t = 0
                for t in range(min(len(piles[i]), rest)):
                    sum_t += piles[i][t]
                    res = max(res, sum_t + A[rest - t - 1])
                B[rest] = res
            A = B
        return A[-1]


piles = [[37,88],[51,64,65,20,95,30,26],[9,62,20],[44]]
k = 9
print(Solution().maxValueOfCoins(piles, k))